/*
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。


链接：https://leetcode.cn/problems/3sum
 */

package LC0015;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

// 暴力求解
// 三重循环，去除重复的数组
// TODO 时间复杂度??
//
public class Solution1 {
    public static void main(String[] args) {
        int[] nums = {-1,0,1,2,-1,-4};

        Solution1 solution = new Solution1();
        System.out.println(solution.threeSum(nums));
    }

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++)
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> temp = new ArrayList<Integer>();
                        temp.add(nums[i]);
                        temp.add(nums[j]);
                        temp.add(nums[k]);
                        //判断结果中是否已经有 temp 。
                        if (isInList(list, temp)) {
                            continue;
                        }
                        list.add(temp);
                    }
                }
        }
        return list;
    }

    // TODO 为什么这些方法不需要是static ???
    public boolean isInList(List<List<Integer>> list, List<Integer> answer) {
        // 遍历List<List<Integer>>，看List<Integer>是否在里面
        for (int i = 0; i < list.size(); i++) {
            //判断两个 List 是否相同
            if (isSame(list.get(i), answer)) {
                return true;
            }
            // TODO 这里为什么不能用equals() ???
        }
        return false;
    }

    public boolean isSame(List<Integer> a, List<Integer> b) {
        int count = 0;
        // 给List<Integer>排序
        Collections.sort(a);
        Collections.sort(b);    // list的排序有先成的方法啊。

        //排序后判断每个元素是否对应相等
        for (int i = 0; i < a.size(); i++) {
            if (a.get(i) != b.get(i)) {
                return false;
            }
        }
        return true;
    }
}
